class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length != inorder.length) {
            return null;
        }
        return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }

        // 根节点值
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);

        // 在中序遍历中找到根节点的位置
        int rootIndexInInorder = inStart;
        while (rootIndexInInorder <= inEnd && inorder[rootIndexInInorder] != rootVal) {
            rootIndexInInorder++;
        }

        // 左子树节点数
        int leftTreeSize = rootIndexInInorder - inStart;

        // 递归构建左子树
        root.left = buildTree(preorder, preStart + 1, preStart + leftTreeSize, inorder, inStart, rootIndexInInorder - 1);
        // 递归构建右子树
        root.right = buildTree(preorder, preStart + leftTreeSize + 1, preEnd, inorder, rootIndexInInorder + 1, inEnd);

        return root;
    }

    // 测试方法
    public static void main(String[] args) {
        Solution solution = new Solution();

        int[] preorder = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] inorder = {4, 7, 2, 1, 5, 3, 8, 6};

        TreeNode root = solution.buildTree(preorder, inorder);
        printTree(root);
    }

    // 打印树的工具方法
    public static void printTree(TreeNode root) {
        printTree(root, 0, "Root: ");
    }

    public static void printTree(TreeNode node, int level, String prefix) {
        if (node != null) {
            System.out.println(repeat(" ", level * 4) + prefix + node.val);
            printTree(node.left, level + 1, "L--- ");
            printTree(node.right, level + 1, "R--- ");
        }
    }

    // 重复字符串的工具方法
    public static String repeat(String str, int count) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < count; i++) {
            sb.append(str);
        }
        return sb.toString();
    }
}
